package algorithm.dynamic;


import org.junit.Test;

/**
 * @author bingo
 * @Description  背包问题
 * @Date 2018/9/2
 */
public class SatchelSolution {
    public int[][] solution(int[] weight,int [] value,int capacity){
        int  result[][] = new int[weight.length][capacity+1];
        for(int i=0;i<weight.length;i++){
            for(int j=0;j<=capacity;j++) {
               if (i == 0) {
                   if (j<weight[i]) {
                       result[i][j] = 0;
                   } else {
                       result[i][j] = value[i];
                   }

               }else {
                    if (j<weight[i]) {
                        result[i][j] = result[i-1][j];
                    }
                    else{
                            int v1 = result[i - 1][j];
                            int v2 = value[i];
                            int w1 = weight[i];
                            if (j - w1 > 0) {
                                v2 = v2 + result[i - 1][j - w1];
                            }
                            result[i][j] = Math.max(v1, v2);
                    }
                }
            }
        }
        return  result;
    }

    public static void main(String[] args) {
        SatchelSolution satchelSolution = new SatchelSolution();
        //int[][] res = satchelSolution.solution(new int[]{5,4,6,3},new int[]{10,40,30,50},10);
        int[][] res = satchelSolution.solution(new int[]{1,2,3,5},new int[]{6,10,12,30},20);
        for(int i=0;i<res.length;i++){
            for(int j=0;j<res[i].length;j++){
                System.out.format("%5d", res[i][j]);
            }
            System.out.println("\t");
        }
    }
    @Test
    public void testMax(){
        System.out.println(Math.max(5,5));
    }
}
